package day07;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给你一个字符串s和一个机器人，机器人当前有一个空字符串t。执行以下操作之一，直到s 和t都变成空字符串：
 *
 * 删除字符串s的 第一个字符，并将该字符给机器人。机器人把这个字符添加到 t的尾部。
 * 删除字符串t的最后一个字符，并将该字符给机器人。机器人将该字符写到纸上。
 * 请你返回纸上能写出的字典序最小的字符串。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "zza"
 * 输出："azz"
 * 解释：用 p 表示写出来的字符串。
 * 一开始，p="" ，s="zza" ，t="" 。
 * 执行第一个操作三次，得到 p="" ，s="" ，t="zza" 。
 * 执行第二个操作三次，得到 p="azz" ，s="" ，t="" 。
 * 示例 2：
 *
 * 输入：s = "bac"
 * 输出："abc"
 * 解释：用 p 表示写出来的字符串。
 * 执行第一个操作两次，得到 p="" ，s="c" ，t="ba" 。
 * 执行第二个操作两次，得到 p="ab" ，s="c" ，t="" 。
 * 执行第一个操作，得到 p="ab" ，s="" ，t="c" 。
 * 执行第二个操作，得到 p="abc" ，s="" ，t="" 。
 * 示例 3：
 *
 * 输入：s = "bdda"
 * 输出："addb"
 * 解释：用 p 表示写出来的字符串。
 * 一开始，p="" ，s="bdda" ，t="" 。
 * 执行第一个操作四次，得到 p="" ，s="" ，t="bdda" 。
 * 执行第二个操作四次，得到 p="addb" ，s="" ，t="" 。
 *
 *
 */
public class Solution4 {
    public String robotWithString(String s) {
        Deque<Character> stack = new LinkedList<>();
        char[] chars = s.toCharArray();
        int []charT=new int[26];
        for (char aChar : chars) {
            charT[aChar-'a']++;
        }
        int min=0;
        StringBuilder str = new StringBuilder();
        for (char aChar : chars) {
            charT[aChar-'a']--;
            while (min<25&&charT[min]==0){
                min++;
            }
            stack.push(aChar);
            while (!stack.isEmpty()&&stack.peek()-'a'<=min){
                str.append(stack.pop());
            }
        }
        return str.toString();
    }
}
